{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "16fed94a-06f7-4155-9d87-5f480e6baaac",
   "metadata": {},
   "source": [
    "# 一、 Jaccard相似度\n",
    "\n",
    "判断两个集合是否相等，一般使用称之为Jaccard相似度的算法（后面用Jac(S1,S2)来表示集合S1和S2的Jaccard相似度）。举个列子，集合X = {a,b,c}，Y = {b,c,d}。那么Jac(X,Y) = 2 / 4 = 0.50。也就是说，结合X和Y有50%的元素相同。下面是形式的表述Jaccard相似度公式：\n",
    "\n",
    "$\\text{Jac}(X, Y) = \\frac{|X \\cap Y|}{|X \\cup Y|}$\n",
    "\n",
    "也就是两个结合交集的个数比上两个集合并集的个数。范围在[0,1]之间。 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "b26c3d74-1035-4b01-aab4-c9cad5de3f62",
   "metadata": {},
   "outputs": [],
   "source": [
    "def jaccard_similarity(set1, set2):\n",
    "    # 计算交集\n",
    "    intersection = len(set1.intersection(set2))\n",
    "    # 计算并集\n",
    "    union = len(set1.union(set2))\n",
    "    # 计算 Jaccard 系数\n",
    "    return intersection / union"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "16ac1040-a630-4059-8074-4111d7d031eb",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Jaccard 相似度: 0.40\n"
     ]
    }
   ],
   "source": [
    "# 示例集合\n",
    "set_a = {\"apple\", \"cherry\", \"banana\"}\n",
    "set_b = {\"banana\", \"cherry\", \"date\", \"fig\"}\n",
    "\n",
    "# 计算 Jaccard 相似度\n",
    "similarity = jaccard_similarity(set_a, set_b)\n",
    "print(f\"Jaccard 相似度: {similarity:.2f}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73888254-7769-4a87-a124-aec1a9dc1d0c",
   "metadata": {},
   "source": [
    "# 二、降维技术Minhash\n",
    "\n",
    "原始问题的关键在于计算时间太长。如果能够找到一种很好的方法将原始集合压缩成更小的集合，而且又不失去相似性，那么可以缩短计算时间。Minhash可以帮助我们解决这个问题。\n",
    "举个例子，S1 = {a,d,e}，S2 = {c, e}，设全集U = {a,b,c,d,e}。集合可以如下表示：\n",
    "\n",
    "| 行号 | 元素 | S₁ | S₂ | 类别 |\n",
    "|------|------|----|----|------|\n",
    "| 1    | a    | 1  | 0  | Y    |\n",
    "| 2    | b    | 0  | 0  | Z    |\n",
    "| 3    | c    | 0  | 1  | Y    |\n",
    "| 4    | d    | 1  | 0  | Y    |\n",
    "| 5    | e    | 1  | 1  | X    |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "fb0cffb1-ee90-4f70-be2c-5198f7327753",
   "metadata": {},
   "source": [
    "其中值1表示s1集合中有元素,0表示没有这个元素，\n",
    "那么minihash 如何实现这种降为的\n",
    "\n",
    "假设我们定义两个简单的哈希函数\n",
    "我们使用两个哈希函数：\n",
    "- $h_1(i) = (2i + 1) \\mod 5$\n",
    "- $h_2(i) = (3i + 2) \\mod 5$\n",
    "\n",
    "生成结果如下\n",
    "| 行号 | $h_1(i)$ | $h_2(i)$ |\n",
    "|------|-------------|-------------|\n",
    "| 1    | 3           | 0           |\n",
    "| 2    | 0           | 1           |\n",
    "| 3    | 2           | 4           |\n",
    "| 4    | 4           | 2           |\n",
    "| 5    | 1           | 3           |\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7e5e664c-1278-4b58-a523-9b97658fd3b7",
   "metadata": {},
   "source": [
    "我们对集合 $S_1 = \\{a, d, e\\}$ 和 $S_2 = \\{c, e\\}$ 计算最小哈希值：\n",
    "\n",
    "- 对 $S_1$：\n",
    "  - $h_1(S_1) = \\min\\{h_1(1), h_1(4), h_1(5)\\} = \\min\\{3, 4, 1\\} = 1$\n",
    "  - $h_2(S_1) = \\min\\{h_2(1), h_2(4), h_2(5)\\} = \\min\\{0, 2, 3\\} = 0$\n",
    "\n",
    "- 对 $S_2$：\n",
    "  - $h_1(S_2) = \\min\\{h_1(3), h_1(5)\\} = \\min\\{2, 1\\} = 1$\n",
    "  - $h_2(S_2) = \\min\\{h_2(3), h_2(5)\\} = \\min\\{4, 3\\} = 3$\n",
    "\n",
    "因此，签名矩阵为：\n",
    "\n",
    "| 集合 | $h_1$ | $h_2$ |\n",
    "|------|----------|----------|\n",
    "| \\( S_1 \\) | 1        | 0        |\n",
    "| \\( S_2 \\) | 1        | 3        |"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "e9e6e8a2-e6a3-46a7-b370-42701bcc51e8",
   "metadata": {},
   "source": [
    "签名的相似度为签名列中相等的比例：\n",
    "$$\n",
    "\\text{Sim}_{\\text{MinHash}}(S_1, S_2) = \\frac{\\text{匹配列数}}{\\text{总列数}}\n",
    "$$\n",
    "\n",
    "对于签名矩阵：\n",
    "- $S_1$ 和 $S_2$ 的签名列 $[1, 0]$ 和 $[1, 3]$\n",
    "- 匹配列数为 $1$（即 $h_1$ 相等）\n",
    "\n",
    "相似度为：\n",
    "$$\n",
    "\\text{Sim}_{\\text{MinHash}}(S_1, S_2) = \\frac{1}{2} = 0.5\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ae715281-2701-409d-ac4d-2e5947fe8850",
   "metadata": {},
   "source": [
    "MinHash 提供了一种近似方法，它的结果 0.50.5 与实际相似度 0.25 存在偏差，但在大量哈希函数下可以收敛到真实值。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "950d2b60-272e-45c4-a877-3d90ac7b0a69",
   "metadata": {},
   "source": [
    "通过上面的方法处理过后，一篇文档可以用一个很小的签名矩阵来表示，将文档进行了压缩，比如使用了30个hash函数。那么就将一篇文档压缩成了30位表示，节省下很多内存空间；但是，还有一个问题没有解决，那就是如果有很多篇文档，那么如果要找出相似度很高的文档，其中一种办法就是先计算出所有文档的签名矩阵，然后依次两两比较签名矩阵的两两；这样做的缺点是当文档数量很多时，要比较的次数会非常大。那么我们可不可以只比较那些相似度可能会很高的文档，而直接忽略过那些相似度很低的文档。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "1ecf2b0d-1f3e-4242-be41-4567c84ed145",
   "metadata": {},
   "source": [
    "threshold (float)\n",
    "设定 Jaccard 相似度的阈值，默认值为 0.9。只有当两个集合的 Jaccard 相似度高于这个阈值时，MinHashLSH 才会将它们识别为匹配。\n",
    "0.0 到 1.0，值越高，匹配的集合之间的相似度要求越高\n",
    "\n",
    "num_perm (int, optional)\n",
    "意义：\n",
    "指定 MinHash 哈希函数的数量，默认为 128。更多的哈希函数可以提高估计的精度，但也会增加计算和存储成本。\n",
    "* 在标准 MinHash 中：表示生成的哈希签名的长度。\n",
    "* 在 weighted-MinHash 中：对应样本规模大小（即权重总和的划分次数）。\n",
    "\n",
    "增大 num_perm 可以提高相似度估计的精确度，但计算量也会随之增加。\n",
    "\n",
    "weights (tuple, optional)\n",
    "意义：\n",
    "优化 Jaccard 相似度阈值的权重，用于加权 MinHash 的计算。它允许对集合中不同的特征（例如不同的维度）分配不同的重要性。\n",
    "默认值为 (0.5, 0.5)，表示均匀权重。\n",
    "在某些情况下，可以为某些维度分配更高的权重以反映其更高的相关性。\n",
    "\n",
    "params (tuple, optional)\n",
    "意义：\n",
    "用于设置 LSH 中 band 的数量和每个 band 的哈希规模：\n",
    "bands 的数量：将哈希签名分为多少组。\n",
    "每个 band 的规模：每组中包含多少个哈希值。\n",
    "原理：LSH 使用 banding 技术，将长的 MinHash 签名分组并分别处理。通过调整 params，可以平衡查全率（recall）和查准率（precision）。\n",
    "建议：\n",
    "适当地调整 params 可以提高 LSH 的性能，具体值需要根据数据集的规模和目标相似度范围来选择。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "c00e4509-d8d5-4271-b027-5bd429b14d28",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
